/*
 * Алгоритм Флойда-Уоршелла
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
#include <limits.h>

#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))
#define MAX(a, b)	((a) > (b) ? (a) : (b))

/* {{{ memory allocation wrappers */
extern void *s_calloc(size_t n, size_t size)
{
	void *ptr;
	ptr = calloc(n, size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern void *s_malloc(size_t size)
{
	void *ptr;
	ptr = malloc(size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern void *s_realloc(void *oldptr, size_t newsize)
{
	void *newptr;
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
	return newptr;
}
/* }}} */

int
floyd_warshall(int **am, int **parent, const int n)
{
	register int j = 0;
	int i = 0, k = 0;
	int max = -1;

	for (; i < n; i++)
		for (j = 0; j < n; j++)
			parent[i][j] = (am[i][j] == -1) ? -1 : i;

	for (k = 0; k < n; k++) {
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				if (am[i][k] != -1 && am[k][j] != -1
						&& (am[i][j] == -1 || am[i][j] > am[i][k] + am[k][j])) {
					am[i][j]   = am[i][k] + am[k][j];
					parent[i][j] = parent[k][j];
				}
			}
		}
	}

	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			max = MAX(max, am[i][j]);

	return max;
}

int
main(void)
{
	int **am, **parent;
	int i, j, n;

	scanf("%d", &n);
	am   = s_calloc(n, sizeof *am);
	parent = s_calloc(n, sizeof *parent);
	for (i = 0; i < n; i++) {
		am[i]   = s_calloc(n, sizeof **am);
		parent[i] = s_calloc(n, sizeof **parent);
	}

	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			scanf("%d", &am[i][j]);

	printf("%d\n", floyd_warshall(am, parent, n));

	for (i = 0; i < n; i++) {
		free(am[i]);
		free(parent[i]);
	}
	free(am);
	free(parent);
	return 0;
}
